import std.string,std.stdio;

const N=1000000000; //2N+1もintの範囲内
const K=9; //N=10^K．コンパイル時にチェックできない？

class ZeroDivException : Exception {
  this() { super("Division by zero!"); }
}

class AbsMinusError : Error {
  this() { super("Absolute value nust not be negative!"); }
}

class BigConvError : Error {
  this() { super("String cannot convert to Bignum!"); }
}

int[] toabs(string s) {
  if(s.length==0) throw new BigConvError();

  int i;
  while(i<s.length && s[i]=='0') i++; //先頭0は無視
  if(i==s.length) return [];

  if(s.length-i!=countchars(s[i..$],"0-9")) throw new BigConvError();

  int[] a;
  int j=s.length;

  while(j-K>=i) {
    a~=atoi(s[j-K..j]);
    j-=K;
  }
  if(i<j) a~=atoi(s[i..j]);

  return a;
}

Bignum tobig(string s) {
  if(s.length==0) throw new BigConvError();

  int sign; int[] abs;

  switch(s[0]) {
    case '-':
      sign=-1;
      abs=toabs(s[1..$]);
      break;
    case '+':
      sign=1;
      abs=toabs(s[1..$]);
      break;
    default:
      sign=1;
      abs=toabs(s);
  }

  if(abs.length==0) sign=0;
  return new Bignum(sign,abs);
}

Bignum tobig(int n) { return new Bignum(n); }
Bignum tobig(uint n) { return new Bignum(n); }
Bignum tobig(long n) { return new Bignum(n); }
Bignum tobig(ulong n) { return new Bignum(n); }

int[] toabs(uint n) {
  if(n==0) return [];

  if(n>=N) {
    return [cast(int)(n%N),cast(int)(n/N)];
  } else {
    return [cast(int)n];
  }
}

int[] toabs(ulong n) {
  if(n==0) return [];

  int[] abs;
  while(n>=N) {
    abs~=cast(int)(n%N);
    n/=N;
  }
  abs~=cast(int)n;

  return abs;
}

int[] toabs(int n) {
  if(n<0) throw new AbsMinusError();
  return toabs(cast(uint)n);
}

int[] toabs(long n) {
  if(n<0) throw new AbsMinusError();
  return toabs(cast(ulong)n);
}

string tos(int[] abs) {
  assert(abs.length==0 || abs[$-1]>0);

  if(abs.length==0) return "0";

  char[] s;
  char[] fom=format("%%0%dd",K);

  for(size_t i=0; i<abs.length-1; i++) {
    s=format(fom,abs[i])~s;
  }
  s=format("%d",abs[$-1])~s;

  return cast(string)s;
}

class Bignum {
  int sign;
  int[] abs; //中身は書き換えないこと. 2.0ならinvariant？

  invariant() {
    foreach(int i; abs) assert(i>=0 && i<N);
    assert(abs.length==0 || abs[$-1]>0);
    if(abs.length>0) {
      assert(sign==1 || sign==-1);
    } else {
      assert(sign==0);
    }
  }

  static Bignum zero() { return new Bignum(); }

  this() {}

  this(int s, int[] a) {
    sign=s;
    abs=a;
  }

  this(uint n) {
    sign = n>0 ? 1 : 0;
    abs = toabs(n);
  }

  this(ulong n) {
    sign = n>0 ? 1 : 0;
    abs = toabs(n);
  }

  this(int n) {
    if(n>=0) {
      this(cast(uint)n);
    } else {
      this();
      sign=-1;
      abs=toabs(-cast(long)n);
    }
  }

  this(long n) {
    static assert(-long.max-1==long.min);

    if(n>=0) {
      this(cast(ulong)n);
    } else {
      this();
      sign=-1;
      abs = n!=long.min ? toabs(cast(ulong)-n) : toabs(cast(ulong)long.max+1);
    }
  }

  override string toString() {
    return sign==-1 ? "-"~tos(abs) : tos(abs);
  }
}

int bigcomp(Bignum n, Bignum m) { // n>m => 1, n==m => 0, n<m => -1
  if(n.sign>m.sign) return 1;
  if(n.sign<m.sign) return -1;

  if(n.sign==1) return abscomp(n.abs,m.abs);
  if(n.sign==-1) return abscomp(m.abs,n.abs);

  assert(n.sign==0 && m.sign==0);
  return 0;
}

int abscomp(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);

  size_t ln=n.length, lm=m.length;

  if(ln>lm) return 1;
  if(lm>ln) return -1;

  while(ln>0 && n[ln-1]==m[ln-1]) ln--;
  if(ln==0) return 0;

  if(n[ln-1]>m[ln-1]) {
    return 1;
  } else {
    assert(m[ln-1]>n[ln-1]);
    return -1;
  }
}

Bignum bigminus(Bignum n) {
  return new Bignum(-n.sign,n.abs);
}

Bignum bigadd(Bignum n,Bignum m) {
  if(n.sign==m.sign) {
    return new Bignum(n.sign,absadd(n.abs,m.abs));
  } else if(n.sign>m.sign) {
    return abssub(n.abs,m.abs);
  } else {
    return abssub(m.abs,n.abs);
  }
}

Bignum bigsub(Bignum n, Bignum m) {
  return bigadd(n, bigminus(m));
}

int[] absadd(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);

  if(n.length>=m.length) {
    return absadd2(n,m);
  } else { 
    return absadd2(m,n);
  }
}

// nの方がケタ多い
int[] absadd2(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);
  assert(m.length<=n.length);

  if(m.length==0) return n;

  int[] c;
  size_t ln=n.length, lm=m.length;
  c.length=ln+1;

  int r=0;
  size_t i=0;
  for( ; i<lm; i++) {
    int t=n[i]+m[i]+r;
    r=(t>=N);
    c[i] = r ? t-N : t;
  }

  for( ; r && i<ln; i++) {
    int t=n[i]+1;
    r=(t==N);
    c[i] = r ? 0 : t;
  }

  if(i<ln) {
    assert(r==0);
    c[i..ln]=n[i..ln];
    c.length=ln;
  } else if(r) {
    c[ln]=1;
  } else {
    c.length=ln;
  }

  return c;
}

int[] delzero(int[] n) {
  size_t i=n.length;
  while(i>0 && n[i-1]==0) i--;
  if(i>0) {
    return n[0..i];
  } else {
    return [];
  }
}

Bignum abssub(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);

  size_t ln=n.length, lm=m.length;
  if(ln>lm) {
    return new Bignum(1,abssub2(n,m));
  } else if(lm>ln) {
    return new Bignum(-1,abssub2(m,n));
  }

  while(ln>0 && n[ln-1]==m[ln-1]) ln--;
  if(ln==0) return Bignum.zero();

  if(n[ln-1]>m[ln-1]) {
    return new Bignum(1,abssub2(n[0..ln], delzero(m[0..ln])));
  } else {
    return new Bignum(-1,abssub2(m[0..ln], delzero(n[0..ln])));
  }
}

// nの方が大きい
int[] abssub2(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);
  assert(abscomp(n,m)>=0);

  size_t ln=n.length, lm=m.length;
  if(lm==0) return n;

  assert(0<lm && lm<=ln);
  int[] c;
  c.length=ln;

  int r=0;
  int max=-1;
  size_t i=0;

  for( ; i<lm; i++) {
    int t=n[i]-m[i]-r;
    if(t>=0) {
      r=0;
    } else {
      t+=N;
      r=1;
    }
    if(t!=0) max=i;
    c[i]=t;
  }

  for( ; r; i++) {
    int t=n[i]-1;
    if(t>0) {
      r=0;
      max=i;
      c[i]=t;
    } else if(t==0) {
      r=0;
      c[i]=0;
    } else {
      max=i;
      c[i]=N-1;
    }
  }

  if(i<ln) {
    c[i..ln]=n[i..ln];
    c.length=ln;
  } else {
    c.length=max+1;
  }

  return c;
}

Bignum bigmul(Bignum n, Bignum m) {
  int[] abs=absmul(n.abs, m.abs);

  if(abs.length>0) {
    int sign = n.sign==m.sign ? 1 : -1;
    return new Bignum(sign,abs);
  } else {
    return Bignum.zero();
  }
}

int[] absmul(int[] n, int[] m) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);

  size_t ln=n.length, lm=m.length;
  if(ln==0 || lm==0) return [];

  int[] c;
  c.length=ln+lm;

  for(int i=0; i<lm; i++) {
    int r=0;

    for(int j=0; j<ln; j++) {
      long t = cast(long)n[j] * m[i] + r;
      assert(t <= cast(long)N*N-N);

      int s = c[i+j] + cast(int)(t%N);

      if(s>=N) {
        c[i+j]=s-N;
        r=cast(int)(t/N)+1;
      } else {
        c[i+j]=s;
        r=cast(int)(t/N);
      }
      assert(r<N);
    }

    assert(c[ln+i]==0); //条件c[ln+i..$]=0は書けない？
    c[ln+i]=r;
  }

  if(c[ln+lm-1]==0) c.length=ln+lm-1;
  assert(c[ln+lm-2]!=0);

  return c;
}

//3ケタ÷2ケタ(≤N)
int div32(int[] a, int[] b) {
  assert(a.length==3 && b.length==2);
  assert(a[2]>0 && b[1]>0 && a[1]>=0 && a[0]>=0 && b[0]>=0);
  assert(a[2]<N && a[1]<N && a[0]<N && b[1]<N && b[0]<N);
  assert(a[2]<b[1] || (a[2]==b[1] && a[1]<=b[0]));

  long la=(cast(long)a[2]*N+a[1])/(b[1]+1);
  assert(0<la && la<N);
  int A=cast(int)la;

  Bignum bb = abssub(a,absmul([A],b));
  assert(bb.sign==1 && abscomp(bb.abs,[0,N-1,1])<0);

  long B;
  for(int i=bb.abs.length-1; i>=0; i--) B=B*N+bb.abs[i];
  long lb=cast(long)b[1]*N+b[0];

  int ret=A + cast(int)(B/lb);
  assert(ret<N || (a[2]==b[1] && a[1]==b[0] && ret==N));
  return ret;
}

//商<Nの割算, rは余り
int divN(int[] n, int[] m, out int[] r) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length>0 && m[$-1]>0);
  assert(abscomp(n,[0]~m)<0);

  size_t ln=n.length, lm=m.length;
  if(lm>ln) { r=n; return 0; }

  assert(lm==ln || lm+1==ln);
  if(ln==1) {
    r = n[0]%m[0] ? [n[0]%m[0]] : [];
    return n[0]/m[0];
  }

  if(ln==2) {
    long l = cast(long)n[1]*N+n[0];
    long k = lm==2 ? cast(long)m[1]*N+m[0] : m[0];
    long lr = l%k;
    r = lr>=N ? [cast(int)(lr%N),cast(int)(lr/N)] : [cast(int)(lr)];
    return cast(int)(l/k);
  }

  int p;
  if(lm==ln) {
    long k=cast(long)n[$-1]*N+n[$-2];
    long l=cast(long)m[$-1]*N+m[$-2];
    if(k<l) { r=n; return 0; }
    p = cast(int)(k/l);
  } else {
    p = div32(n[$-3..$],m[$-2..$]);
  }
  assert(p>0 && p<=N);

  if(p==N) {
    p=N-1;
    assert(abscomp(n,absmul(m,[N-1]))>=0);
  }

  Bignum bb=abssub(n,absmul(m,[p]));
  if(bb.sign>0) {
    r=bb.abs;
  } else if(bb.sign<0) {
    p-=1;
    bb=abssub(m,bb.abs);
    assert(bb.sign==1);
    r=bb.abs;
  } else {
    r=[];
  }

  return p;
}

int[] absdiv(int[] n, int[] m) {
  int[] r;
  return absdiv(n,m,r);
}

int[] absmod(int[] n, int[] m) {
  int[] r;
  absdiv(n,m,r);
  return r;
}

int[] absdiv(int[] n, int[] m, out int[] rem) {
  assert(n.length==0 || n[$-1]>0);
  assert(m.length==0 || m[$-1]>0);

  if(m.length==0) throw new ZeroDivException();
  if(n.length<m.length) { rem=n; return []; }

  n=n.dup;
  size_t ln=n.length;
  int[] c;
  c.length=n.length;

  while(true) {
    size_t i=ln-m.length+1;
    assert(1<=i && i<=ln);

    if(abscomp(n[i-1..ln],m)<0) i--;
    if(i==0) {
      rem=n[0..ln];
      break;
    }

    int q; int[] r;
    q=divN(n[i-1..ln],m,r);

    assert(q>0);
    c[i-1]=q;
    if(i==1) { rem=r; break; }

    assert(i>=2);
    if(r) {
      ln=i-1+r.length;
      n[i-1..ln]=r;
    } else {
      while(i>1 && n[i-2]==0) i--;
      ln=i-1;
    }

    if(ln<m.length) {
      rem = n[0..ln];
      break;
    }
  }

  return delzero(c);
}

Bignum bigdiv(Bignum n, Bignum m) {
  int[] abs=absdiv(n.abs, m.abs);

  if(abs.length>0) {
    int sign = n.sign==m.sign ? 1 : -1;
    return new Bignum(sign,abs);
  } else {
    return Bignum.zero();
  }
}

Bignum bigmod(Bignum n, Bignum m) {
  int[] abs=absmod(n.abs, m.abs);

  if(abs.length>0) {
    int sign = n.sign==m.sign ? 1 : -1;
    return new Bignum(sign,abs);
  } else {
    return Bignum.zero();
  }
}
